// https://www.lintcode.com/problem/modern-ludo-i/

public class Solution {
    /**
     * @param length: the length of board
     * @param connections: the connections of the positions
     * @return: the minimum steps to reach the end
     */
    public int modernLudo(int length, int[][] connections) {
        // Write your code here
        // 7步的情况：1的话走1步到2，走6步到7，丢1次足够了...
        if (length <= 7) {
            return 1;
        }
        int[] sc = new int[length + 1];
        int[] dp = new int[length + 1];
        sc[0] = 0;
        dp[0] = 0;
        for (int i = 1; i <= length; ++i) {
            sc[i] = i; // 自己和自己一定短路
            dp[i] = length;
        }
        dp[1] = 0; // 一开始就在位置1
        for (int i = 0; i < connections.length; ++i) {
            sc[connections[i][0]] = connections[i][1]; // 短路表内容
        }
        for (int i = 2; i <= length; ++i) {
            if ((i - 6) <= 1) {
                dp[i] = 1; // 丢1次肯定能到
            } else {
                for (int j = i - 1; j > i - 7; --j) { // 往前看6步
                    dp[i] = Math.min(dp[j] + 1, dp[i]); // j丢1次肯定能到i
                }
            }
            dp[sc[i]] = Math.min(dp[i], dp[sc[i]]); // 更新第i个点对应的短路位置
        }
        return dp[length];
    }
}